#include "shearSort.h"

// ------------------- CONSTRUCTORS AND DESTRUCTORS ----------------------
ShearSort::ShearSort(){

}

ShearSort::~ShearSort(){

}

//-------------------- PUBLIC METHODS ------------------------------------

// Sort items with ShearSort algorithm
// For vertical and horizontal phases use BubbleSort algorithm
void ShearSort::sort(Array * a){
    unsigned long itemsCnt = a->getCnt(), rowsCnt = sqrt(itemsCnt), colsCnt = itemsCnt / rowsCnt, ii=-1;
    int * items = a->getArray();
    BubbleSort * bs = new BubbleSort();

    if(rowsCnt * colsCnt != itemsCnt) colsCnt++;

    unsigned long offset = rowsCnt * colsCnt - itemsCnt;
//    cout << rowsCnt << ", " << colsCnt << ", " << offset << endl;

    while(true){
        ii++;

        // Horizontal phase - first row can be incomplete
        bs->sort(items, 0, colsCnt-offset - 1);

        unsigned long start = colsCnt-offset;
        bool desc = true;

        for(unsigned long jj=1;jj<rowsCnt;jj++){
//            cout << start << ", " << start + colsCnt - 1 << endl;
            bs->sort(items, start, start + colsCnt - 1, desc);
//            cout << start << ", " << start + colsCnt - 1 << endl;
            start += colsCnt;
            desc = !desc;
        }

        if(!(++ii < ceil(2*log2(rowsCnt)+1))) break;

        // Vertical phase
        for(unsigned long jj=0;jj<colsCnt;jj++){
            bs->sort(items, jj-offset, itemsCnt-1, colsCnt);
        }
    }

    delete bs;
}
